Sistemas Operativos (página 2)

Schedullers: Componente del sistema operativo responsable de decidir quien hara uso de la CPU.

Algoritmos de Schedulling.-

FCFS (First Come First Served)

Cuando un proceso llega a la cola de ready su PCB es agregado al final de la lista. El uso de la CPU es otorgado al primero de la lista y una vez que un proceso comienza a ejecutar no deja de hacerlo hasta que se termina. El tiempo medio de espera para este algoritmo suele ser bastante alto.

SJF (Shortest Job First)

Una vez que un proceso ejecuta no deja de hacerlo hasta que voluntariamente cambia de estado (no hay interrupción por tiempo). Asocia a cada proceso el tiempo de CPU que habrá de usar en su próxima vuelta y va a decidir por el más pequeño. Si hubiera mas de uno utiliza FCFS para desempatar. El mayor problema de este algoritmo radica en el cálculo de tiempo de uso de CPU.

El problema de este algoritmo es que el tiempo de espera para los procesos largos puede ser demasiado largo. Constantemente se están entregando los procesos mas cortos y el más grande nunca será ejecutado.

El FJS se puede subdividir en 2 tipos de algoritmos: PREEMPTIVO o NO PREEMPTIVO

Preemptivo significa que si mientras un proceso se esta ejecutando, entra a la cola de ready un proceso mas corto, el proceso en la cola de ready se apropia de la CPU y comienza su ejecución.

Priority Schedulling

Asocia a cada proceso una prioridad. Luego selecciona el proceso con mas prioridad para desempatar. En caso de que hubieran dos o mas procesos con la misma prioridad, se usa FCFS para desempatar. Hay dos tipo de prioridad en los procesos: la prioridad externa definidas a través del sistema operativo y la prioridad interna definida por el tiempo de uso de la CPU, el control de E/S, etc. Este algoritmo también se puede ejecutar de dos maneras: preemptivo y no preemptivo. El algoritmo soluciona el problema del looping pero el problema es que los procesos con prioridad muy baja tienen chance de no ejecutarse nunca. Para solucionar este problema de espera infinita el envejecimiento de un proceso eleva su prioridad.

Round Robin

Este es un algoritmo basado en FCFS. Trata la cola de ready como una lista circular. Introduce el concepto de "Quantum" o "Time slice" : mayor tiempo de cpu que podrá hacer uso un proceso en cada vuelta. Si el valor del Quantum fuese muy grande, el algoritmo funcionara como un FCFS. Si el Quantum fuera muy chico se produce un overhead por context switch (significa que el Quantum se setea en un tiempo menor al que demora el context switch). Este algoritmo es fuertemente dependiente del Quantum o Time Slice. El Quantum debe ser mayor que el 80% de los tiempos de CPU que hagan uso los procesos, pero no el proceso entero sino por cada burst.

MQS (Multilevel Queue Schedulling)

Este algoritmo parte la cola de ready en un numero de colas n. Luego existe un criterio para clasificar en que cola será colocado un proceso cuando que queda en estado de ready. Cada cola puede manejar su propio algoritmo de schedulling

MFQS (Multilevel Feed Back Queue Schedulling)

Define los siguientes parámetros:

• Numero de colas

• Algoritmo de schedulling usado en cada cola

• Método para decidir a que cola entrara un proceso cuando entre a estado de ready

• Método para decidir cuando un proceso será enviado a una cola de menor prioridad.

Múltiple CPU

Para que mas de una CPU no tomen el mismo proceso de la cola de ready se utilizan mecanismos de sincronización. Otro mecanismo seria partir la cola en n colas (n CPUs), pero si se hiciera esto podría llegar a suceder que los procesos de una CPU fueran todos cortos y los de otra fueran largos por lo cual habría una CPU que quedaría libre y otra ejecutando. Otra forma sería que una CPU decidiera cual CPU va a ejecutar cual proceso. Esto puede llevar a que la CPU que esta seleccionando quede un poco mas cargada porque en algún momento estará ejecutando el algoritmo de selección y un proceso asignado a ella.

Comunicación entre procesos.-

Hay dos tipos de procesos: los independientes que no afectan ni pueden ser afectados por ningún otro proceso y los cooperativos que afectan y pueden ser afectados por algún otro proceso del sistema operativo.

Los procesos con frecuencia precisan comunicarse entre si, Para esto existen ciertos contratiempos que debieron ser superados. Para prevenir este problema en las situaciones en la que interviene cualquier recurso compartido se debe impedir que mas de un proceso haga uso del recurso compartido al mismo tiempo. Lo que se necesita es exclusión mutua, La parte del programa que accesa la memoria compartida se le llama sección crítica. Para tener una solución adecuada los procesos deben cumplir estos cuatro puntos:

• 1. Nunca dos procesos pueden encontrarse simultáneamente en sus secciones críticas.

• 2. No se hacen suposiciones acerca de las velocidades relativas de los procesos o del numero de CPU.

• 3. Ningún proceso suspendido fuera de la sección crítica debe bloquear a otros procesos.

• 4. Nunca un proceso debe querer entrar en forma arbitraria en su sección crítica.

Algoritmos de Soluciona al Problema de Sección Critica

Técnicas con Espera Ocupada

Deshabilitación de Interrupciones

La solución mas simple es que cada proceso desactive todas las interrupciones justo después de entrar en su sección crítica y las vuelva a activar antes de salir de ella. Con las interrupciones deshabitadas no pueden ocurrir interrupciones al reloj por lo cual no se cambiara a otro proceso. Este método no es muy atractivo ya que no es muy prudente dar a los procesos del usuario el poder de desactivar las interrupciones.. Si un usuario lo hiciera y nunca las volviera a activar sería el fin del sistema. Además si fuera un sistema con mas de una CPU la desactivación de interrupciones solo afectaría una de ellas y las otras podrían accesar la memoria compartida.

Algoritmo de Variables de Cierre

Este algoritmo utiliza un flag. Al entrar a la sección crítica se fija si es uno o cero si es cero lo pone en uno y entra a la sección crítica; si es uno espera hasta que valga cero. Antes de salir de la sección crítica iguala el flag a cero.

Repeat

If (flag = 0) then {

Flag:=1

Seccion crítica

Flag:=0

Seccion no crítica}

Until 0 = 1

Este algoritmo si embargo no resuelve el problema de la sección crítica porque si hubiera una interrupción justo después de comprobar el estado del flag y se accediera a la memoria compartida antes de cambiar el flag, otro proceso podría acceder a la memoria compartida, cambiar el flag a uno y habrían dos procesos accesando la memoria compartida.

Algoritmo de alternación Estricta

En este algoritmo dos procesos comparten una variable flag, pero en vez de utlizar el mismo codigo se usa distinto codigo para cada proceso.

El problema aquí radica en que si un proceso tiene una sección no crítica muy larga el otro tendrá que esperar para entrar en su sección crítica a pesar qe no se este ejecutando nada que la afecte.

Algoritmo de Peterson (o Algoritmo de Dekker)

Este algoritmo combina las dos ideas anteriores. Se comparten una variable flag y una variable turno.

Este algoritmo soluciona el problema de la sección crítica y evite que un proceso quede en espera mientras que otro proceso este en su sección no crítica. Para n procesos la idea es un poco mas compleja:

Flag::array[0..n-1]

Turn::0..n-1

El while se tornara en una evaluación de n condiciones

Semáforos

Son una herramienta de sincronización. Es una variable protegida que solo puede ser modificada por la rutina de inicialización y por otras dos operaciones atómicas:

P( ) signal(a) : Habilita la ejecución de algún proceso en espera por la ejecución de la instrucción wait con la misma variable de condición.

Deadlocks

Si un conjunto de procesos esta en estado de espera por recursos y nunca cambia de estado porque los recursos por los que espera están siendo utilizados por otros procesos en estado de espera tenemos un DEADLOCK. Los recursos son la memoria, dispositivos de E/S, semáforos, archivos, etc. La forma en que un proceso hace uso de un recurso es:

Solicitud: si el recurso esta disponible se le otorga, si no el proceso pasa a estado de espera.

Uso: El proceso utiliza el recurso

Liberación: el proceso debe liberar el recurso.

Condiciones Necesarias para que se produzca DEADLOCK

Si se presentan simultáneamente las cuatro siguientes condiciones el sistema esta en DEADLOCK.

• 1. EXCLUSION MUTUA: Por lo menos un proceso que tenga otorgado un recurso en forma exclusiva.

• 2. USO Y ESPERA: Debe existir al menos un proceso que este haciendo uso de un recurso y que este esperando por otros recursos asignados a otros procesos.

• 3. NO INTERRUPCION: Los recursos no pueden ser retirados al proceso. Si un proceso hace uso de un recurso no le podrá ser retirado hasta que voluntariamente el proceso lo libere.

• 4. ESPERA CIRCULAR: Debe existir un conjunto de procesos {P1…..Pn} tal que P1 espera por un recurso utilizado por P2,……,Pn espera por un recurso utilizado por P1.

Resourse Allocation Graph(Grafo de utilizacion de recursos)

Conjunto de Vértices: U =P U R

P={P1,P2,….,Pn}

R={R1,R2,…,Rn}

Conjunto de Aristas:

Una arista de un proceso Pi a un Recurso Rj significa que el proceso i esta haciendo una solicitud por el recurso Rj.

Una arista del recurso Rj al proceso Pi, significa que el recurso esta asignado al proceso.

Si un RAG no tiene ciclos el sistema no esta en DEADLOCK, sis si los tiene no se puede afirmar nada.

Mecanismos para tratar con Deadlocks

Prevención de Deadlocks

La estrategia consiste en anular alguna de las cuatro condiciones necesarias para que se produzca un Deadlock.

• 1. No puede ser anulada porque existen recursos que deben ser usados en modalidad exclusiva.

• 2. La alternativa sería hacer que todos los procesos solicitaran todos los recursos que habrán de utilizar antes de utilizarlos al momento de su ejecución lo cual sería muy ineficiente.

• 3. Para anular esta condición cuando un proceso solicita un recurso y este es negado el proceso deberá liberar sus recursos y solicitarlos nuevamente con los recursos adicionales. El problema es que hay recursos que no pueden ser interrumpidos.

• 4. Espera Circular: esta estrategia consiste en que el sistema operativo numere en forma exclusiva los recursos y obligue a los procesos a solicitar recursos en forma ascendente. El problema de esto es que quita posibilidades a la aplicación.

Evasion de Deadlocks

Si se tiene cuidado al en la forma de asignar los recursos se pueden evitar situaciones de Deadlock. Supongamos un ambiente en el que todos los procesos declaren a priori la cantidad máxima de recursos que habá de usar.

Estado Seguro: un estado es seguro si se pueden asignar recursos a cada proceso (hasta su máximo) en algún orden sin que se genere Deadlock. El estado es seguro si existe un ordenamiento de un conjunto de procesos {P1…Pn} tal que para cada Pi los recursos que Pi podrá utilizar pueden ser otorgados por los recursos disponibles mas los recursos utilizados por los procesos Pj,j<i. Si los recursos solicitados por Pi no pueden ser otorgados, Pi espera a que todos los procesos Pj hayan terminado.

Algoritmo del banquero de Dijkstra

Asigna peticiones de recursos siempre que las mismas den como resultado estados seguros. Solicitudes que den como resultado estados inseguros serán negadas hasta que puedan ser satisfechas. Este algoritmos evita situaciones de Deadlock asignando los recursos en forma correcta.

Las debilidades del algoritmo son: que requiere que la cantidad de recursos del sistema sea constante, requiere una cantidad de procesos constante y requiere que los procesos garanticen que los recursos van a ser devueltos en un intervalo finito de tiempo.

Detección y Recuperación de Deadlocks

Algoritmos de Detección de Deadlock

• Cuando hay una única ocurrencia de cada recurso. (variante del grafo de "wait for graph"). Consiste en reducir el grafo, retirando las aristas que van de recursos a procesos y de procesos a recursos, colocando nuevas aristas que reflejan la situación de espera entre procesos. Si el grafo reducido tiene ciclos el sistema esta en Deadlock. Orden de operaciones = n^2 , n = cantidad de aristas.

• Cuando hay múltiples ocurrencias de cada recurso

Procedure detecta_deadlock

var Disponible:array[1..n] of integer //# de recursos

Usados:array[1..n] of integer

Solicitados:array[1..n] of integer

Finalizado:array[1..n] of boolean

Begin

Work:=Disponibles;

For i:=1..n do if(usados[i]?0) then finish[i]:=false

Else finish[i]:=true;

While(encontrar_indice_i = true) do {

Work:=work + usados[i];

Finish[i]:=true; }

If ((finish[i] = false) para algun i), 1=i=n then ( El sistema esta en Deadlock.

End

Function encontrar_indice_i : Boolean

Begin

If (existe i tal que (Finish[i]=false && solicitados[i] = work)

Then -> true

Else -> false

End

Recuperación ante Deadlocks

• Cancelación de procesos

• Cancelación de todos los procesos involucrados. Esto resuelve la situación de Deadlock pero tiene un costo muy alto de reprocesamiento.

• Cancelacion de un proceso por vez hasta resolver la situación de Deadlock. La ventaja de esto es que el costo de reprosesamiento de la información es menor pero cada vez que se cancela un proceso debe ejecutarse el algoritmo de detección de deadlock. Los criterios para elegir el candidato a ser cancelado son: por prioridad, por tiempo de uso de CPU, por cantidad de recursos utilizados y por cuantos recursos adicionales habrá de utilizar.

• Obtención de recursos (resourse Preemption). El sistema operativo selecciona un proceso y le quita los recursos otorgados. Los criterios para seleccionar el candidato son los mismos que para la cancelación. El proceso seleccionado se le quitan los recursos y se le lleva a un estado consistente (Rollback).

Memoria

Utilización de la memoria.-

Los programas residen en disco como ejecutables binarios y deben ser traídos a memoria para su ejecución. El conjunto de programas residentes en disco esperando para ser cargados en memoria forman la cola de entrada.

Los programas pueden direccionar memoria en varias formas:

• 1. Direccionamiento al momento de la compilación: se genera código absoluto (es decir que siempre ejecuta en una dirección de memoria de inicio fija, si esta ocupada no ejecuta)

• 2. Direccionamiento al momento de la carga: maneja direcciones relativas al momento de carga del programa (no genera código absoluto). Se generan direcciones relativas a la posición inicial de memoria (desplazamiento).Genera código reubicable.

• 3. Dinamic Linking: se difiere la link edición hasta el momento de ejecución se usa normalmente con bibliotecas del sistema. Al momento de la link edición (generación del ejecutable) se entrega un trozo de código indicando la referencia a la rutina que se debe cargar.

• 4. Overlays: Esta técnica permite ejecutar un programa en un espacio de memoria menor que su tamaño. Mantiene en memoria toda aquella parte del programa que es utilizada en un instante determinado. Las rutinas independientes son cargadas a medida que se necesitan ejecutar (son partes del programa que se dividen en forma independiente).

Administración de Memoria Real.-

Asignación contigua de almacenamiento de un solo usuario.-

• Un solo usuario a la vez

• Todos los recursos a disposición de un solo usuario

• El tamaño de los programas esta limitado por la cantidad de memoria, aunque se pueden usar overlays para sacar mayor provecho a esta.

Protección de Memoria: Se incorpora un registro de limite (limit register) a la cpu. Cada petición de acceso a la memoria realizada por el usuario se compara con el registro limite. Si la dirección a la que se quiere acceder es menor o igual al registro limite se cancela la solicitud.

Multiprogramación de partición fija.

La memoria se divide en particiones de tamaño fijo (puede ser distinto el tamaño de cada partición).

Originalmente los programas se compilaban y link editaban para ejecutar en una partición en particular (direcciones absolutas). Posteriormente los compiladores y link editores generan código reubicable para que un programa pudiera ejecutar en cualquier partición de memoria suficientemente grande.

Con esta estructura de administración de memoria se desperdicia memoria y tiempo de CPU (si hay un programa corriendo los demás quedan encolados aunque haya otra partición libre).

Multiprogramación de partición variable.-

Cada programa o usuario utiliza tanta memoria como sea necesaria siempre que quepa en el almacenamiento real. Cuando los programas van terminando su ejecución se van generando agujeros en memoria.

Métodos de solucion al problema de agujeros en meoria:

Combinación.-

Cuando un programa termina su ejecución el sistem,a operativo verifica si hay algun bloque de memoria contigua libre (antes o después) en cuyo caso los combina para generar un único bloque de memoria libre de tamaño igual a la suma de ambos.

Compactación o Compresión.-

Agrupa toda la memoria disponible en un único bloque de memoria al final.

Desventajas:

• Alto consumo de CPU (casi dedicada exclusivamente a esto)

• Mientras se ejecuta el algoritmo la actividad del sistema debe ser detenida.

• La movida de programas implica reubicación

En definitiva no es conveniente utilizar este método para solucionar el problema de los agujeros en memoria debido al alto costo.

Estrategias de colocación en el almacenamiento.-

En cualquiera de estas estrategias cuando a una petición le es asignada una partición y sobra memoria el sistema operativo se da cuenta y deja a este espacio sobrante como una nueva partición.

Best Fit.-

Los bloques de memoria son asignados según las necesidades del programa que se esta ejecutando

First fit.-

Asignan la primera partición disponible en la que pueda entrar el programa. Esta estrategia es mas rápida pero se desperdicia mucho espacio de memoria.

Worst Fit.-

Consiste en asignar la partición en la que sobra mas espacio.

Almacenamiento de Memoria Virtual.-

Las direcciones de memoria no están necesariamente contenidas en el almacenamiento real. El S.O. se apoya en el almacenamiento secundario para extender el uso de la memoria.

Las direcciones referidas por los procesos son direcciones virtuales. Los procesos no tienen por que saber en que posición de almacenamiento real o secundario están almacenados. Las direcciones de memoria que direcciones de memoria que referencian al almacenamiento primario (memoria real) se denominan "direcciones reales". Por mas que los procesos hagan referencia a direcciones virtuales, estos solo pueden ejecutar en el almacenamiento primario; por lo tanto las direcciones virtuales deben ser transformadas en direcciones reales mientras el proceso esta en ejecución.

Como el almacenamiento real es compartible por varios procesos solo se mantiene al mismo tiempo una pequeña parte de cada uno de ellos en memoria real.

El mecanismo de traducción de direcciones deberá mantener mapas que ilustren que direcciones del almacenamiento virtual se encuentran en memoria real, y donde se encuentran.

La información se agrupa en bloques y el sistema operativo debe estar informado del lugar en que se encuentra almacenada cada página).

bloque. Cuando los bloques son del mismo tamaño se denominan páginas y el mecanismo de administración del almacenamiento virtual asociado se denomina paginación.

Si los bloques son e tamaño variable se denominan segmentos y el mecanismo de administración del almacenamiento virtual segmentación.

Las direcciones en un esquema de almacenamiento virtual son un par (b,d) donde b indica el bloque y d el desplazamiento desde el inicio del bloque.

Paginación

Las direcciones en un sistema de paginación están dadas por:

Las páginas se transfieren del almacenamiento secundario al primario en bloque llamados page frames (los cuales tienen el mismo tamaño de las páginas).

El sistema lleva una tabla de páginas para cada proceso. De esta forma se asegura la protección.

Cuando un proceso debe ser cargado en memoria par ejecutar se siguen determinados pasos:

• 1. Se calcula su tamaño en páginas

• 2. Se carga el programa en memoria

• 3. se construye la tabla de paginas del proceso.

Soporte de Hardware.-

Como la tabla de páginas de cada proceso puede llegar a tornarse demasiado grande, se buscan mecanismos que permiten acelerar el tiempo de búsqueda en esa información. La solución mas simple es la utilización de un conjunto de registros dedicados (no usar tabla de paginación de cada proceso). El CPU dispatcher será el encargado de cargar y actualizar la información de estos registros con cada context switch. Esta solución sería razonable si se hablara de pocos registros pero en la realidad no se utiliza.

La solución mas común es apoyarse en un cache de acceso muy rápido llamado TLB (Translation Location Buffer). La TLB solo puede contener algunas entradas de la tabla de páginas. Con cada context switch la TLB debe ser variada para evitar que un proceso haga referencia a direcciones de memoria utilizadas por otro proceso (protección). Si se hace referencia a una dirección que no estaba cargada en TLB, se debe cargar en esta, eliminando alguna otra dirección si fuera necesario.

Protección.-

Por la forma en que se construyen las tablas de página los procesos solo van a hacer referencia a direcciones de su espacio virtual. La protección se implementa por un conjunto de bits que son asociados a cada frame. Un bit puede definir si una página es read-only o read-write y cada vez que se hace una operación sobre un page frame se verifica sobre estos bits.

Multilevel Paging.-

En algunos sistemas se busca minimizar el tiempo de búsqueda en la tabla de páginas utilizando un sistema de paginación de 2 niveles.

Una dirección es de la forma: (P1,P2,d) donde P1 y P2 corresponde al número de página y d al desplazamiento.

Inverted Page Table.-

Se lleva una tabla de páginas para todos los procesos. Cada entrada de página contiene la siguiente información:

Paginas Compartidas.-

Es posible que los procesos compartan código común (reentrante) El código común no podrá ser modificado durante su ejecución, por lo cual se deberán proteger mediante los bits de protección.

Segmentación.-

En un esquema de segmentación un espacio de direcciones lógicas es un conjunto de segmentos. Cada segmento tendrá un nombre y un largo. Las direcciones van a hacer referencia tanto al nombre como al desplazamiento dentro del segmento.

Mecanismo de traduccion de direcciones.-

Se lleva un tabla de segmento por cada proceso, cada entrada a la tabla de segmento lleva la siguiente informacion: segment base (dirección base del segmento)

segment limit (largo del segmento)

Protección.-

La protección se asegura verificando cada acceso a la memoria con la tabla de segmentos para asegurar que se esta direccionando dentro del espacio de direcciones lógicas del proceso.

Además el mecanismo de traducción de direcciones asegura que no se direccione fuera de un segmento en particular. Existen también bits de protección para cada entrada de la tabla de segmentos que indicaran si el segmento es read only o read-write.

Segmentos Compartidos.-

Similar a lo visto para paginación. Se comparte la totalidad de un segmento

Fragmentación.-

El sistema operativo deberá asignar memoria utilizando algunos algoritmos ya vistos (first fit, worst fit, best fit) Cuando el sistema operativo intenta cargar un segmento y no hay ningún segmento disponible de tamaño suficiente para almacenarlo se procederá a compactar la memoria.

Paginación por demanda.-

Es similar a lo visto para la paginación introduciendo el concepto de swapping. Los procesos residen en el disco y al ser ejecutados deben ser cargados en memoria. Cuando un proceso va a ser ejecutado, el mismo es swappeado a memoria, utilizando lazy swapping. El lazy swapping nunca trae paginas a memoria si no van a ser ejecutadas. Se necesita determinar si un pagina esta en memoria o en disco, por lo cual se utiliza el bit de válido / inválido de la tabla de páginas. Si el bit = 1 la página es valida y esta cargada en memoria si es 0 la página es inválida y no esta cargada en memoria (esta en disco).

Cuando un proceso intenta acceder a una página que no esta cargada en memoria ocurre un page fault (tomo de página). El procedimiento para manejar un page fault es el siguiente:

• 1. Verificar si la referencia a la pagina es valida (se utiliza una tabla interna (generalmente llevada en PCB) donde se indica las paginas validas.

• 2. Si la referencia no es valida, se cancela la ejecución del proceso.

• 3. Encontrar un frame disponible para cargarla (la página esta en disco)(por ejemplo de la free frame list)

• 4. Solicitar operación de I/O para leer la página de disco cargarla en el frame obtenido.

• 5. Modificar la tabla interna y la tabla de paginas para que ahora esta pagina figure como que esta en memoria.

• 6. Continuar con la ejecución del proceso en la instrucción en la que fue interrumpido.

Reemplazo de Página.-

Si al momento de generarse un page fault no hubiera ningún frame disponible, se debe proceder a reemplazar una pagina de memoria. LA rutina de page fault debe ser modificada para incluir reemplazo de páginas:

• 1. Encontrar un frame disponible.

• 2. Si hay un frame disponible usarlo

• 3. Si no hay frames disponibles utilizar algoritmo de reemplazo de paginas para seleccionar la víctima

• 4. Escribir la pagina víctima a disco y actualizar tabla de paginas .

Algoritmos de remplazo de página

FIFO (Firs In First Out).-

Asocia a cada página el tiempo en que fue cargada en memoria. Cuando debe reemplazar una página, se selecciona la que hace mas tiempo que esta en memoria. También se puede implementar mediante la utilización de una lista. Se reemplazan las páginas de la cabeza y se agregan al final.

LRU (Least Recently Used).-

Se selecciona la página que hace mas tiempo que no se utiliza. Asocia cada página el tiempo de la última vez que fue utilizada. En LRU se necesita llevar tiempo de última utilización de cada página:

Contadores: Se asocia a cada entrada en la tabla de páginas, el tiempo de la última vez que se uso. Cada vez que se accede a una página se actualiza el contador.

Stack: Se lleva un stack con los números de página cada vez que una página es accedida, se quita del stack y se quita al tope. En el tope del stack estará la página que fue utilizada por última vez, y en el fondo la página que hace mas tiempo que no se accede.

Algoritmo de Segunda Chance.-

Es una variante del algoritmo FIFO. Cada vez que se selecciona una página, se inspecciona un bit de referencia. Si el valor es cero se procede a reemplazar la página. Si el valor es uno, se da una segunda oportunidad a la página y se selecciona la siguiente víctima por criterio FIFO. Cada vez que una página recibe una segunda oportunidad, se carga en ceo el bit de referencia. Si una página vuelve a ser accedida, se incrementa el bit de referencia a uno.

LFU (Least Frequently Used).-

Establece que la página con menos cantidad de referencias debe ser reemplazado. Una contra del algoritmo es que una página puede haber sido muy utilizada en la fase de carga de un proceso, pero no ser vuelta a utilizar, por lo cual se estaría manteniendo en memoria páginas que no son necesarias para la ejecución.

MFU (Most Frequently Used).-

La pagina con mayor cantidad de referencias es la víctima a ser reemplazada. El argumento es que si una pagina fue utilizada pocas veces, se debe a que recién fue cargada en memoria y aún deba ser utilizada.

Page Buffering.-

Se lleva un pool de frames disponibles. Cuando ocurre un page fault se elige una víctima utilizando alguno de los mecanismos ya vistos (anteriores). En lugar de hacer el cambio de frame en una sola operación se carga la pagina en memoria en uno de los frames disponibles (pool) permitiendo que el proceso retome su ejecución. El S. O. Se encargará luego de descargar la página y agregarla al pool de frames disponibles (es decir que agrego a la lista de paginas del pool la página liberada en memoria)

Trashing.-

Cuando un proceso consume mas tiempo paginando que ejecutando se dice que el proceso esta en situación de trash. Una forma de evitar esta situación es utilizar un mecanismo de reemplazo de paginas "local". Cuando un proceso comienza a paginar, no puede robar frames de otros procesos solamente podrá reemplazar páginas de su propio proceso.

Working-Set.-

Es el conjunto de la páginas activas de un proceso que son almacenadas en memoria. Se define un número n por proceso. Las n páginas más activas del proceso son mantenidas en memoria.

PFF (Page Fault Frequency).-

Se controla el page fault rate de cada proceso. Si un proceso tiene page fault rate muy bajo probablemente se deba a que este utilizando demasiados frames en memoria. Si el page fault rate es muy alto, probablemente no tenga sufiecientes frames otorgados. La idea de esta técnica es definir limite superior e inferior para page fault.

Prepaginado.-

Es una estrategia para evitar el alto nivel de paginación inicial, consiste en cargar en memoria de una vez todas las páginas que el proceso necesite.

Segmentación por demanda.-

Un proceso no necesita tener todos los segmentos cargados en memoria para ejecutar. Solamente se deben cargar en memoria aquellos que estén siendo activamente utilizados. La tabla de segmentos mantiene un bit de validez (idem paginación por demanda) para indicar si un segmento esta en memoria o en disco. Cada vez que se direcciona un segmento se chequea el bit de validez. Si el segmento no esta cargado en memoria se produce un segmento fault. Una vez detectada la necesidad de un segment fault, se utiliza la siguiente técnica:

• 1. Verificar si hay suficiente memoria libre para acomodar el segmento. Si no hay suficiente memoria libre, se puede llegar a utilizar compactación de memoria

• 2. Si luego de la compactación sigue sin haber espacio para acomodar el segmento se debe producir un reemplazo de segmento.

• 3. El segmento al final de la lista es seleccionado y es swappeado a disco.

• 4. Si el nuevo espacio libre es suficientemente grande para acomodar el segmento de carga. Si no se repite el paso 3. hasta obtener un espacio suficientemente grande.

File Systems

Atributos: nombre, tipo, tamaño, protección (información de control de acceso asociado), fecha y hora de creación, fecha y hora de modificación, usuario propietario.

Operaciones sobre archivos:

• Crear archivo: implica encontrar espacio disponible donde ubicar el archivo y ademas crear una entrada en el directorio.

• Escribir a un archivo: implica ubicar el archivo en la estructura de directorios e invocar a una system call que se encargue de escribir la informacion.

• Leer desde archivo: implica ubicar el archivo en la estructura de directorios e invocar a una system call que se encargue de realizar la lectura.

• Borrar un archivo: implica ubicar un archivo en la estructura de de directorios, eliminar su referencia y además liberar el espacio ocupado.

Para minimizar los tiempos de búsqueda en la estructura de directorios se suele llevar una tabla de archivos abiertos. La primera vez que un archivo es referenciado se agrega su referencia a esta tabla. Cuando los archivos dejan de ser utilizados se procede a cerrarlos eliminándolos de la tabla.

Estructuras de directorios.-

Single Level Directory.-

Todos los archivos son contenidos en un único directorio, lo cual hace que la búsqueda sea muy fácil pero no se pueden repetir los nombres de archivos.

Two Level Directory.-

Cada usuario va a tener un single level directory lo cual soluciona el problema de los nombres. Estos directorios de cada usuario se llaman UFD (User File Directory). Se mantiene un directorio MFD (Master File Directory) el cual indica dado un usuario que directorios posee. El problema de esta estructura es que no permite los archivos compartidos.

Estructura de Árbol.-

Esta es la estructura más común. Existe un directorio raíz que contiene un conjunto de archivos y subdirectorios. Hay un bit en la estructura de directorios que indica si una entrada es un archivo o un subdirectorio.

Grafo Acíclico.-

Si un archivo puede estar referenciado por dos o mas entradas de un directorio el sistema operativo deberá proveer mecanismos que eviten procesar mas de una vez la información en operación que recorren la estructura de directorios. El sistema operativo debe llevar una lista de referencias de los archivos (file reference list) para poder determinar en que momento se debe liberar el espacio ocupado al borrar un archivo.

Grafos.-

Los algoritmos de búsqueda en la estructura de directorios deben contemplar la posibilidad de entrar en loop infinito.

Implementación de File Systems.-

Método de Asignación Contigua.-

Cada vez que se crea un archivo el mismo es almacenado en disco en forma contigua (conjuntos de bloques contiguos en disco). Simplifica los mecanismos de acceso a la información del archivo. La estructura de directorios sería:

Los archivos no se pueden extender, se les asigna el disco cuando se crea con un tamaño que se cree conveniente, por mas que los cálculos sean buenos, se puede llegar a desperdiciar espacio.

La dificultad es que no siempre se tiene la información del espacio que halla e ocupar un archivo al momento de su creación.Asignación Encadenada.-

Cada archivo en un conjunto de bloques encadenados que pueden estar distribuidos en cualquier lugar del disco. Los archivos pueden crecer libremente siempre que haya espacio en sico. Para encontrar el bloque i-ésimo es necesario i bloques en memoria para poder seguir la cadena.

Variante: Tabla FAT (Ms-DOS)

Asignación Indexada.-

Cada archivo mantiene un bloque que indica en donde se almacena los puentes a todos los bloques ocupados por el archivo. Un archivo puede crecer libremente y en la búsqueda es más rápido. Soluciona los problemas de la asignación continua (los archivos pueden crecer libremente mientras haya espacio en disco y espacio en el archivo de índices). El problema de este método es que se puede producir pérdida de espacio ya que cada archivo por chico que sea tiene un bloque índice. Por otro lado existe un límite para el tamaño de un archivo dado por la cantidad de índices. La ventaja del método es la velocidad en el acceso a la información en el archivo.

Manejo de espacio libre.-

La lista de espacio libre (Free Sapce List), que lleva información de todos los bloques de disco que no estén siendo ocupados por ningún archivo o directorio. Cada vez que un archivo es creado, el sistema operativo recorre esta lista asignando los bloques necesarios.

Implementación de la lista de espacio libre.-

Bit Vector (Vector de Bits).-

La lista de espacio libre es llevada como un vector de bits, donde 1 indica que el bloque esta ocupado y 0 indica un bloque libre. Es simple encontrar cual es el primer bloque disponible, o n bloque consecutivo. El problema es que la técnica deja de ser eficiente a menos que el vector sea cargado en memoria principal, lo que puede ser un problema.

Lista Encadenada.-

Llevar una estructura de lista donde estén encadenadas la información de todos los bloques libres en disco. Se lleva en memoria un puntero al primer bloque libre. Esta técnica no es eficiente para asignación contigua

Implementación de Directorios.-

Lista Encadenada.-

Consiste en llevar una lista de nombres de archivos con punteros a los bloques de datos. La búsqueda de esta implementación consume considerable tiempo cada vez que se referencia a un archivo, debe recorrerse toda la estructura de la lista.

Hash.-

Consiste en llevar una estructura de hash para representar la información de directorio. El principal problema de esta implementación es fijar el largo de la tabla de hash.

Si la tabla es muy grande (como es un vector) la búsqueda es rápida pero se desperdicia mucho espacio. Si la tabla es chica los tiempos de búsqueda casi como los de la lista encadenada.

Estructura del Almacenamiento Secundario.-

Estructura de disco.-

Las direcciones en disco son referidas como una dirección compuesta, donde se incluye el numero de dispositivo, la cara, la pista y el sector. El conjunto de sectores que pueden ser leídos sin que se muevan las cabezas del disco se denominan cilindro. El sector es la menor unidad que puede ser leída o escrita de un disco.

Los tiempos involucrados en una operación de E/S son:

• Tiempo de búsqueda: es el tiempo que le lleva al disco mover las cabezas hasta llegar a la pista adecuada.

• Tiempo de latencia: es el tiempo que demora el disco en girar hasta ubicar el sector dentro de la pista

• Tiempo de transferencia: es el tiempo que lleva transferir la información entre la memoria y el disco.

Mientras el disco esta resolviendo una solicitud, las solicitudes adicionales serán encoladas en cola de E/S. Existen algoritmos para resolver mas eficientemente el problema de cómo ordenar la cola de E/S.

Algoritmos de Selección de Cola de I/O

FCFS (First Come Firs Served).-

Se accede a las direcciones en el disco de la misma forma en que fueron entrando.

SSJF (Shortest Seek Time First).-

La idea es servir juntos todos los requerimientos que estén cerca de la posición actual de la cabeza del disco. Los requerimientos que están muy apartados de la posición de la cabeza no van a ser tomados en cuenta nunca (la cola es dinámica, siempre están llegando requerimientos). Es decir que pueden haber requerimientos que no sean satisfechos nunca o que sean postergados indefinidamente.

Scan.-

Propone resolver todos los requerimientos en el sentido en que se esta moviendo la cabeza del disco hasta llegar a su extremo o a que no hay requerimientos para resolver en ese sentido, en cuyo caso comienza a resolver en sentido contrario.

C-Scan.-

Similar al anterior pero los requerimientos se resuelven siempre en el mismo sentido. Si no hay mas requerimientos para satisfacer en ese sentido o se llegó al extremos del disco se salta al comienzo del mismo y se continúa resolviendo.

Formateo.-
Formateo Físico.-

Consiste en escribir un conjunto de sectores en el disco en cada pista que las cabezas puedan leer. Cada uno de estos sectores contiene el numero de sector, información de ECC (error Correctin Code) el cual permite identificar errores en la lectura de un sector del disco. Cada vez que se escribe un sector se calcula un valor aplicando una formula a todos los bytes del sector y se almacena en este. Al momento de leer el sector, se recalcula el valor y se compara con el valor guardado. Si son distinto el sector puede estar dañado y el sistema operativo puede decidir marcarlo como malo. (bad blocks).

Formateo Lógico.-

Inicializa la información del file systems: directorio vacío, información de i-nodos, fat, etc, free space list, etc.

Manejo del espacio de Swap.-

El espacio de swap puede ser utilizado de diferentes maneras dependiendo del sistema operativo en cuestión. El espacio de swap puede residir en el file system o en una partición separada. Si es un archivo mas las primitivas normales del file system se utilizan para crearlo, asignarle espacio, escribirlo, etc. Compite con los demás requerimientos de E/S del file system.

Lo mas común es almacenar el espacio de swap en una partición separada donde no se coloque ningun file sstem ni estructura de directorios (raw devices). Se utilizan algoritmos de gerenciamiento del espacio de swap para asignar y desasignar bloques. La ventaja es la velocidad ya que se evitan las primitivas de E/S del file system y no se compite con la cola de E/S del dispositivo.

Proteccion.-

Refiere a los mecanismo para controlar el acceso de programas, usuarios o proceso a los recursos definido en el sistema. Un sistema es un conjunto de recursos (CPU, memoria, impresoras, etc.) en donde cada objeto o recurso tiene un nombre único. Las operaciones que se pueden hacer sobre cada objeto dependen del objeto.

Dominios de proteccion.-

Cada proceso opera dentro de su dominio de protección, que indica las operaciones que el proceso puede hacer sobre un determinado conjunto de objetos. La habilidad de un proceso de ejecutar una operación sobre un objeto se denomina derecho (acces right). Un dominio es un conjunto de derechos cada uno de los cuales es un par ordenado

Un dominio puede estar definido de varias formas:

Un usuario es un dominio. El conjunto de objetos que pueden ser accedidos dependen de la identidad del usuario.

Un proceso es un domino. El conjunto de objetos que pueden ser accedidos dependen de la identidad del proceso.

Un procedimiento es un dominio.

Matriz de Acceso.-

El modelo de protección puede ser visto mediante una matriz de acceso. Las filas representan dominios y las columnas representan objetos. Las entradas de la matriz representan el conjunto de derechos para el objeto en cuestión, para determinado dominio.

Autor:

Marcelo Bendahan